package 剑指Offer;

import java.util.ArrayList;
import java.util.List;

public class Offer57II_和为s的连续正数序列 {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList<>();
        /*注意本题的窗口就是target转化后的数组，利用俩指针来构建出窗口，其实这个数组并不存在，但是我们可以认为它存在
         只要认为左边界从1开始，右边界不超过target即可
         */
        int left = 1;
        int right = 2;
        int sum = 3;//窗口中的元素和。初始化为3，因为窗口[1,2]的和为3

        while (left < right) {

            if (sum < target) {
                //注意这里要先扩大窗口，再把新的元素加入
                right++;
                sum = sum + right;
            } else if (sum > target) {
                //这里要先减掉将要排除的元素，才可以移动左边界
                sum = sum - left;
                left++;
            } else {
                int[] arr = new int[right - left + 1];
                for (int i = left; i <= right; i++) {
                    arr[i - left] = i;
                }
                res.add(arr);
                //右移左边界缩小窗口。继续寻找
                sum = sum - left;
                left++;
            }

        }

        return res.toArray(new int[res.size()][]);
    }
}

